package leetcode.dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : zx
 * @version V1.0
 */
public class JiaQiLai {

    /**
     *
     * 首先输入几个正整数，不可以重复。比如说 5,6,2,3。然后输入一个target也是正整数，比如说9。现在需要找出前面的那个数组里面选
     * 几个数（可以重复选择）加起来等于这个target。不能输出相同的数组
     * 比如这个例子：
     * 输入：
     * 5,6,2,3
     * 9
     *
     * 输出：
     * [3,3,3] [3,6]
     */

    // 输入数组
    public int[] inputs;
    // 结果列表
    public List<Integer[]> result = new ArrayList<>();
    // 缓存
    public LinkedList<Integer> tmp = new LinkedList<>();
    // 目标结果
    public int target;
    /**
     * 第几个数字
     */
    public void dfs(int index, int sum){
        if (index < this.inputs.length){
            // 预期结果大于目标
            if (sum> target){
                return;
            }
            // 结果相等
            if (sum == target){
                Integer[] a = new Integer[this.tmp.size()];
                this.result.add(this.tmp.toArray(a));
                return;
            }
            // 遍历+递归
            for (int i = index; i < inputs.length; i++){
                this.tmp.push(inputs[i]);
                dfs(i, sum+inputs[i]);
                tmp.pop();
            }
        }
    }

    public List<Integer[]> find(int[] input, int t){
        this.inputs = input;
        this.target = t;
        dfs(0,0);
        return this.result;
    }

    public static void main(String[] args){
        JiaQiLai j = new JiaQiLai();
        List<Integer[]> l = j.find(new int[]{1,3,6,2}, 9);
        for (Integer[] a:l){
            for (Integer b:a){
                System.out.print(b);
                System.out.print(' ');
            }
            System.out.print('\n');
        }
    }
}
